<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <!-- <meta name="viewport" content="width=device-width, initial-scale=1.0"> -->
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>
<body>
    <h3>深拷贝 VS 浅拷贝</h3>

    <!-- 概率：深拷贝和浅拷贝都是针对的引用类型，JS中的变量类型分为值类型（基本类型）和引用类型；
    对值类型进行复制操作会对值进行一份拷贝，而对引用类型赋值，则会进行地址的拷贝，最终两个变量指向同一份数据
        栈区 堆区
    值类型：undefined、null、Boolean、number、string。
    变量直接按指存放在栈区内，可以直接访问，所以我们平时把字符串、数字的值赋值给新变量，相当于把值完全复制过去，新变量的改变不会影响旧变量。

    引用类型：存放在堆区的对象，变量在栈区中保存的是一个指针地址

    对于引用类型，会导致a b指向同一份数据，此时如果对其中一个进行修改，就会影响到另外一个，
    有时候这可能不是我们想要的结果，如果对这种现象不清楚的话，还可能造成不必要的bug
    那么如何切断a和b之间的关系呢，可以拷贝一份a的数据，根据拷贝的层级不同可以分为浅拷贝和深拷贝，浅拷贝就是只进行一层拷贝，深拷贝就是无限层级拷贝 -->

</body>

</html>
<script type="text/javascript">
    /*01 satrt 浅拷贝与深拷贝简单封装*/

    // var a1 = {b: {c: {}}};

    // var a2 = shallowClone(a1); // 浅拷贝
    // console.log(a2.b.c === a1.b.c )// true

    // var a3 = clone(a1); // 深拷贝
    // console.log(a3.b.c === a1.b.c) // false

    // a1.b.c=1
    // console.log(a1.b.c)
    // console.log(a2.b.c)

     /*测试溢出*/
    // console.log(createData(1, 3)); // 1层深度，每层有3个数据 {data: {0: 0, 1: 1, 2: 2}}
    // console.log(createData(3,3)); // 3层深度，每层有0个数据 {data: {data: {data: {}}}}
    // clone(createData(1000)); // 
    // clone(createData(100000)); // Maximum call stack size exceeded 超过最大调用堆栈大小
    // clone(createData(10, 10000)); //  广度不会溢出

    // var a = {};
    // a.a = a;
    // console.log(clone(a))
    /*浅拷贝*/
    function shallowClone(source) {
        var target = {};
        for(var i in source) {
            if (source.hasOwnProperty(i)) {
                target[i] = source[i];
            }
        }
        return target;
    }
    /*深拷贝*/
    function clone(source) {
        var target = {};
        for(var i in source) {
            if (source.hasOwnProperty(i)) {
                // if (typeof source[i] === 'object') {
                if (isObject(source)){
                    target[i] = clone(source[i]); // 注意这里
                } else {
                    target[i] = source[i];
                }
            }
        }

        return target;
        //没有对参数做检验
        //判断是否对象的逻辑不够严谨 比如null
        //没有考虑数组的兼容
    }

    //对象判断
     function isObject(x) {
        return Object.prototype.toString.call(x) === '[object Object]';
    }

    /*递归内存溢出测试*/
    function createData(deep, breadth) {
        var data = {};
        var temp = data;

        for (var i = 0; i < deep; i++) {
            temp = temp['data'] = {};
            for (var j = 0; j < breadth; j++) {
                temp[j] = j;
            }
        }
        return data;
        
    }

     /*02 深拷贝利用JS方法实现*/

    //  var a1 = {b: {c: {}}};

    // var a3 = cloneJSON(a1);
    // console.log(a3.b.c === a1.b.c) // false

    // a1.b.c=1
    // console.log(a1.b.c)
    // console.log(a3.b.c)

    /*测试溢出*/
    /*1*/
    // cloneJSON(createData(10000))
    /*2*/
    // var a = {};
    // a.a = a;
    // cloneJSON(a)
    function cloneJSON(source) {
        return JSON.parse(JSON.stringify(source));
        // 将引用类型转值类型 在再转引用类型返回
    }

    /*02 end*/


    /*03 破解递归爆栈 使用循环实现深拷贝*/
    //     var a = {
    //         a1: 1,
    //         a2: {
    //             b1: 1,
    //             b2: {
    //                 c1: 1
    //             }
    //         }
    //     }
    // var b = cloneLoop(a)
    // b.a1 = 2;
    // console.log(a)
    // console.log(b)



    // 用循环遍历一棵树，需要借助一个栈，当栈为空时就遍历完了，栈里面存储下一个需要拷贝的节点
    // 首先我们往栈里放入种子数据，key用来存储放哪一个父元素的那一个子元素拷贝对象
    // 然后遍历当前节点下的子元素，如果是对象就放到栈里，否则直接拷贝
    function cloneLoop(x) {
        const root = {};

        // 栈
        const loopList = [
            {
                parent: root, //当前拷贝完成的数据
                key: undefined, //当前需要拷贝节点的KEY
                data: x, //下一个需要拷贝的节点
            }
        ];

        while(loopList.length) {
            const node = loopList.pop();
            const parent = node.parent;
            const key = node.key;
            const data = node.data;

            // 初始化赋值目标，key为undefined则拷贝到父元素，否则拷贝到子元素
            let res = parent;
            if (typeof key !== 'undefined') {
                res = parent[key] = {};
            }

            for(let k in data) {
                if (data.hasOwnProperty(k)) {
                    if (typeof data[k] === 'object') {
                        // 下一次循环
                        loopList.push({
                            parent: res,
                            key: k,
                            data: data[k],
                        });
                    } else {
                        res[k] = data[k];
                    }
                }
            }
        }

        return root;
    }
    /*03 end*/

    /*04 破解循环引用 保持引用关系*/
    // 举个例子，假如一个对象a，a下面的两个键值都引用同一个对象b，经过深拷贝后，a的两个键值会丢失引用关系，从而变成两个不同的对象

    // var f = [];
    var b = {
        a:{}
    };
    var a = {a1: b,a2: b};
    console.log(a.a1 === a.a2) // true
    // var c = clone(a);

    var c = cloneForce(a);
    console.log(c.a1 === c.a2) // false

    // 引入一个数组arrList用来存储已经拷贝的数组，每次循环遍历时，先判断对象是否在arrList中了，如果在的话就不执行拷贝逻辑了
    // find是抽象的一个函数，其实就是遍历arrList

    // 如果保持引用不是你想要的，那就不能用cloneForce了；
    // cloneForce在对象数量很多时会出现很大的问题，如果数据量很大不适合使用cloneForce
    function cloneForce(x) {
        // =============
        const arrList = []; // 用来去重
        // =============

        let root = {};

        // 循环数组
        const loopList = [
            {
                parent: root, //当前拷贝完成的数据
                key: undefined, //当前需要拷贝节点的KEY
                data: x, //下一个需要拷贝的节点
            }
        ];

        while(loopList.length) {
            // 深度优先
            const node = loopList.pop();
            const parent = node.parent;
            const key = node.key;
            const data = node.data;

            // 初始化赋值目标，key为undefined则拷贝到父元素，否则拷贝到子元素
            let res = parent;
            if (typeof key !== 'undefined') {
                res = parent[key] = {}; 
            }
            
            // =============
            // 数据已经存在
            let uniqueData = find(arrList, data);
            if (uniqueData) {
                parent[key] = uniqueData.target;
                continue; // 中断本次循环
            }

            // 数据不存在
            // 保存源数据，在拷贝数据中对应的引用
            arrList.push({
                source: data,  // 目标对象
                target: res,  //赋值目标
            });
            // =============
        
            for(let k in data) {
                if (data.hasOwnProperty(k)) {
                    if (typeof data[k] === 'object') {
                        // 下一次循环
                        loopList.push({
                            parent: res,
                            key: k,
                            data: data[k],
                        });
                    } else {
                        res[k] = data[k];
                    }
                }
            }
        }

        return root;
    }
    //将当前需要拷贝的对象
    function find(arr, item) {
        for(let i = 0; i < arr.length; i++) {
            if (arr[i].source === item) {
                return arr[i];
            }
        }

        return null;
    }

    /*测试代码*/
    function runTime(fn, time) {
        var stime = Date.now();
        var count = 0;
        while(Date.now() - stime < time) {
            fn();
            count++;
        }

        return count;
    }

    // console.log(runTime(function () { clone(createData(500, 100)) }, 1000)) //
    // console.log(runTime(function () { cloneJSON(createData(500, 100)) }, 1000)) //
    // console.log(runTime(function () { cloneLoop(createData(500, 100)) }, 2000))
    // console.log(runTime(function () { cloneForce(createData(500, 100)) }, 2000))
    
    // clone 时间 = 创建递归函数 + 每个对象处理时间
    // cloneJSON 时间 = 循环检测 + 每个对象处理时间 * 2 （递归转字符串 + 递归解析）
    // cloneLoop 时间 = 每个对象处理时间
    // cloneForce 时间 = 判断对象是否缓存中 + 每个对象处理时间


    // https://juejin.im/post/5bc1ae9be51d450e8b140b0c  深拷贝的终极探索
</script>